\subsection{An Iterative Multi-Mode Algorithm (IteM)}\label{sec:item}

\subsubsection{Overview}
Our algorithm is denoted by IteM (for Iterative Multi-Mode). IteM starts with a trace signal solution that is optimized for a single-mode, identified as a suitable ``start'' mode ($m_{start}$) which is more likely to yield to the highest $MSSR$. IteM then perturbs this solution iteratively by replacing some of the existing trace signals with the other unselected state elements, in order to improve restoration over all the modes. It has a non-greedy nature based on a gradually-increasing perturbation radius within each iteration. Specifically, at each iteration, up to $R$ number of trace signals in the current solution may be swapped. The process terminates upon observing no improvements in $MSSR$ in 20 consecutive iterations.

One motivation behind IteM is that one operation mode $m$ may have significantly higher potential for restoration compared to many of the other modes. %In the previous example of {\tt S38584} given in Section \ref{sec:ref}, we observe that $SRR^0$ is always much higher than $SRR^1$ in Table \ref{tab:mot}. In this case, starting from the solution of SMTS$^0$ and perturbing it can be a better strategy to improve $MSSR$ than the previous algorithm.
Moreover, working with the initial solution generated by an SMTS procedure for $m_{start}$ allows a faster pace to maximize multi-mode restorability in an iterative procedure.

The specific strengths of IteM are (1) quickly identifying a suitable starting mode and finding its corresponding single-mode solution; (2) considering non-greedy and randomized moves with gradual degree of perturbation when swapping at each iteration; (3) explicit consideration of multi-mode restoration at each swap using the multi-mode impact weight introduced in the previous subsection.

\subsubsection{Identifying the Start Mode and Generating the Initial Solution}
To find $m_{start}$, we first compute the reachability list of each state element for each mode ($L^m_f$ given by Equation \ref{eq:rl}). Recall if a state element is selected as a trace signal, then all the state elements in its reachability list can be restored by it, without the help of any other trace signal. %Also recall, that the reachability list of a state element also depends on the operation mode because the corresponding control signal values are also used to determine if other state elements can be restored.
We then compute $m_{start}$ using the following equation.
\begin{equation}\label{eq:mstart}
m_{start}=\operatorname{argmax}_m(\sum_{\forall f\in F}|L^m_f|)
\end{equation}
where the sizes of the reachability lists of the state elements in a single mode are added, and the mode with the maximum aggregate size is selected. Note, this process requires pre-computing $M\times|F|$ reachability lists (for each state element and each mode), however in practice it is quite fast, e.g., negligible runtime to compute all the reachability lists for a single mode compared to solving SMTS for that mode, as we show in our experiments. In case of mode merging, a representative mode is used instead. So the reachability lists of the state elements are only computed for the representative mode.

After $m_{start}$ is identified, we apply the SMTS algorithm in \cite{LiD13,LiD14TCAD} for initial solution generation due to its fast runtime and relatively good solution quality. This initial solution is used as the basis for the following perturbation steps in order to gradually improve $MSRR$.

\begin{figure}[t]
\centering
    \includegraphics[width=3.5in]{figs/swap.eps}
    \caption{Procedure to swap up to $R$ trace signals per iteration, with gradual increase in perturbation radius $r$}
    \label{fig:swap}
\end{figure}


\subsubsection{Iterative Perturbation of the Current Solution}
Figure \ref{fig:swap} shows the process of swapping up to $R$ trace signals at a single iteration of IteM. We start  by the smallest \emph{radius} of perturbation of $r=1$, corresponding to swapping a single trace signal with one of the remaining state elements. A probabilistic acceptance criteria is used to evaluate the swap.  If the acceptance criteria is satisfied, the swap will be made and the iteration terminates. Otherwise, the radius of perturbation is gradually increased up to $r=R$, as shown in Figure \ref{fig:swap}. This gradual increase in the radius of perturbation increases the likelihood to satisfy the acceptance criteria. If a suitable swap can not be found at the maximum radius, the radius is set back to 1 and a new search starts based on switching to swapping using a random strategy. The process repeats itself using random swapping up to the maximum radius. In the end, if the acceptance criteria is still not satisfied, the random swap strategy is used to swap one signal (without further evaluating the criteria).

Below we explain further details of the algorithms.

{\bf Each swap} is made of two steps: 1) eliminating the least promising trace signal from the current solution, and 2) adding the most promising of the remaining state elements as a trace signal. In the case of random swap, the elimination part is based on random elimination of state elements (and not the least promising one) from the existing trace signals but the addition step remains the same.% (i.e., the most promising state element is found based on the randomly-eliminated trace signal).

{\bf Elimination of the least promising trace signal} is done as follows. For a given trace signal solution with $B$ traces, we consider eliminating each trace signal and compute the corresponding $MSSR$ for the remaining $B-1$ trace signals. (Recall $MSSR$ is given by Equation \ref{eq:msrr} and computed using X-Simulation.) The elimination candidates are ranked with respect to the corresponding $MSSR$ and the top candidate for elimination is the one with the highest $MSSR$ (associated with the remaining signals).%, essentially having the least contribution to the existing solution.%, thus being the best candidate for replacement.

Computing the elimination ranking of $B$ candidates requires $B$ number of $MSSR$ computations involving X-Simulation. To speedup the process, once a (ranked) elimination queue is created and the swaps in one iteration are made, the same queue will continue to be used for a total of 8 iterations. %Note a typical trace buffer bandwidth is up to $B=64$ trace signals.
The eliminations in the remaining 7 iterations is done by just selecting the trace from the top of the list. We observed the above procedure to be a reasonable approximation while providing significant speedup in our simulations.

%We found this approximation can significantly improve the speed without much loss in the final solution quality because the amount of perturbation among consecutive solutions is controlled by the small radius of $R=3$ in our implementation. Moreover, an eliminated trace signal may be added in a future iteration, as we show in our simulation results.



{\bf Addition of the most promising trace signal} is done by ranking the unselected trace signals using their multi-mode impact weights ($MW_f\forall F\in T\setminus T$) given by Equation \ref{eq:mmiw}. Next a small number of top candidates (i.e., 3\% of state elements) with highest $MW_f$ are selected. The best candidate is then found by computing $MSSR$ among the top candidates.

{\bf Applying $r>1$ number of swaps} is done as follows. First $r$ eliminations are done by selecting the $r$ trace signals from the top of the elimination queue. Next $r$ new trace signals with the highest multi-mode impact weights ($MW_f$) are sequentially selected. In this case, every time, a new trace signal is added, the multi-mode impact weights $MW_f$s are also updated.

{\bf To accept one (or more) swaps}, first, we consider the $MSSR$ for the set of trace signals if the swaps are made. (Note, this $MSSR$ is already computed during the addition step when the best candidate is identified.) We denote this by $MSSR_{cur}$. If the $MSSR_{cur}$ is better (higher) than $MSSR_{prv}$ (i.e., the $MSSR$ of the previous solution), then the swap is accepted. Otherwise, it is accepted by following Boltzmann's criteria \cite{SA} ($e^{\frac{MSRR_{cur} - MSRR_{prv}}{T}} >$ $rand$ with $rand$ a randomly generated number between 0 and 1). The parameter $T$ is updated at each iteration to be 0.95 of its value in the previous iteration with an initial value of 10K.


\exclude{
{\bf Elimination of the least promising trace signal} is done as follows. For a given trace signal solution with $B$ traces, we consider eliminating each trace signal and compute the corresponding $MSSR$ for the remaining $B-1$ trace signals. (Recall $MSSR$ is given by Equation \ref{eq:msrr} and computed using X-Simulation.) The elimination candidates are ranked with respect to the corresponding $MSSR$ and the top candidate for elimination is the one with the lowest $MSSR$, essentially having the least contribution to the existing solution, thus being the best candidate for replacement.

Computing the elimination ranking of $B$ candidates requires $B$ number of $MSSR$ computations involving X-Simulation. To speedup the process, once a (ranked) elimination queue is created and the swaps in one iteration are made, the same queue will continue to be used for a total of 8 trace signal selection iterations. Note a typical trace buffer bandwidth is up to $B=64$ trace signals. The eliminations in the remaining 7 iterations will be done by just selecting the trace from the top of the list.

We found this approximation can significantly improve the speed without much loss in the final solution quality because the amount of perturbation among consecutive solutions is controlled by the small radius of $R=3$ in our implementation. Moreover, an eliminated trace signal may be added in a future iteration, as we show in our simulation results.


To add the most promising trace signal, the unselected trace signals are ranked based on their multi-mode impact weights ($MW_f\forall F\in T\setminus T$) given by Equation \ref{eq:mmiw}. Next a few top candidates (i.e., 3\% of state elements) with highest $MW_f$ are selected. The best candidate is then found by computing $MSSR$ among the top candidates. For discussion about the details, please see Section \ref{sec:conm}.

{\bf Applying $r>1$ number of swaps} is done as follows. First $r$ eliminations are done by selecting the $r$ trace signals from the top of the elimination queue. Next up to $r$ new trace signals with the highest $MW_f$s are sequentially added. Note, in this case, every time, a new trace signal is added, the multi-mode impact weights $MW_f$s are also updated.

{\bf To accept one (or more) swaps, a probabilistic criteria} is used. First, we consider the $MSSR$ for the set of trace signals if the swaps are made. (Note, this $MSSR$ is already computed during the addition step when the best candidate is identified.) We denote this by $MSSR_{cur}$. If the $MSSR_{cur}$ is better (higher) than $MSSR_{prv}$ (i.e., the $MSSR$ of the previous solution), then the swap is accepted. Otherwise, it is accepted by following Boltzmann's criteria \cite{SA} ($e^{\frac{MSRR_{cur} - MSRR_{prv}}{T}} >$ $rand$ with $rand$ a randomly generated number between 0 and 1). The parameter $T$ is updated at each iteration to be 0.95 of its value in the previous iteration with an initial value of 10K.
}


\exclude{
Perturbing a solution requires swaps of selected trace signals
with unselected trace signals. Each swap consists of two steps: 1)
eliminating the least promising trace signal from the current solution, and
2) adding the most promising of the remaining state elements as a trace
signal. We also allow random swaps in which the elimination part is based on
random elimination of state elements (and not the least promising one) from
the existing trace signals but the addition step remains the same based on adding the most promising one.

{\bf Elimination of the least promising trace signal} is done as follows. For a given trace signal solution with $B$ traces, we consider eliminating each trace signal and computing the corresponding $MSSR$ for the remaining $B-1$ trace signals.The elimination candidates are ranked with respect to the corresponding $MSSR$ and the top candidate for elimination is the one with the highest $MSSR$, essentially having the least contribution to the existing solution.

Computing the elimination ranking of $B$ candidates requires $B$ number of
$MSSR$ computations involving X-Simulation. To speedup the process, once a
(ranked) elimination queue is created and the swaps in one iteration are
made, the same queue will continue to be used for a total of 8 trace
selection iterations. The eliminations in the remaining 7 iterations will be done
by just selecting the trace from the top of the list. We observe that this approximation can significantly improve the speed without much loss in the final solution quality.

{\bf Addition of the most promising trace signal} is done by first ranking
the unselected trace signals based on their multi-mode impact weights
($MW_f\forall F\in T\setminus T$) given by Equation \ref{eq:mmiw}. Next a
few top candidates (i.e., 3\% of state elements) with the highest $MW_f$ are
selected. The best candidate is then found by computing $MSSR$ through
X-Simulation among the top candidates.

{\bf Swaps are accepted under two situations}. Let's consider the $MSSR$ for the
set of trace signals if swaps are made. (Note, this $MSSR$ is already
computed during the addition step when the best candidate is identified.)
We denote this by $MSSR_{cur}$. In the first case, if the $MSSR_{cur}$ is better (higher) than
$MSSR_{prv}$ (i.e., the $MSSR$ of the previous solution), the swap is
accepted. Otherwise, it is accepted by following the {\bf Boltzmann's criteria} \cite{SA} ($e^{\frac{MSRR_{cur} - MSRR_{prv}}{T}} >$ $rand$ with $rand$ a randomly generated number between 0 and 1). The parameter $T$ is updated at each iteration to be 0.95 of its value in the previous iteration with an initial value of 10K.

By introducing the probabilistic acceptance criteria, IteM can reduce the
risk of solutions being stuck at local optimality. To further avoid
such situations and to accelerate the pace of improvement, we introduce the
strategy of {\bf swapping up to $R$ trace signals at a single iteration} in
the IteM algorithm (We set $R=3$ in our implementation
which is considered a small maximum radius with respect to the trace buffer
bandwidth of up to $B=64$ signals.).

Figure \ref{fig:swap} illustrates the strategy. We start by the smallest
\emph{radius} of perturbation of $r=1$, corresponding to swapping a single
trace signal with one of the remaining state elements. The probabilistic
acceptance criteria is then used to evaluate the swap. The probabilistic nature
helps with {\emph non-greedy} exploration of the search space. If the
acceptance criteria is satisfied, the swap will be made and the iteration
terminates. Otherwise, the radius of perturbation is gradually increased up
to $r=R$. At this maximum radius, we aim
to replace $R$ trace signals from the current solution with $R$ unselected
state elements. This gradual increase in the radius of perturbation
increases the likelihood to satisfy the acceptance criteria.

If a suitable swap can not be found at the maximum radius, the radius is set back to 1 and a new search starts based on switching to swapping using a random strategy. The process repeats itself using random swapping up to the maximum radius. In the end, if the acceptance criteria is still not satisfied, the random swap strategy is used to swap one signal (without further evaluating the criteria).
} 